package map;

import java.util.HashMap;
import java.util.Map;

public class MapProblem {

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
//    public int singleNumber(int[] nums) {
//        //使用HashMap统计每个数字出现的次数
//        //再遍历HashMap，找到只出现了一次的数据
//        Map<Integer,Integer> map = new HashMap<>();
//        for(int num : nums){
//            int count = map.getOrDefault(num,0);
//            map.put(num,count + 1);
//        }
//
//        //遍历该map,找到只出现了一次的数据
//        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
//            if(entry.getValue() == 1){
//                return entry.getKey();
//            }
//        }
//        //正常来说，不会走这个逻辑，会保证数组中一定存在出现次数为1的数
//        return 0;
//    }

    public int singleNumber(int[] nums) {
        int result = 0;
        for(int num : nums){
            result ^= num;
        }
        return result;
    }

    public Node copyRandomList(Node head){
        //1，创建Map，key是旧节点，value是新节点
        Map<Node,Node> map = new HashMap<>();
        //2,遍历旧连边，依次创建新节点，插入到map中去
        for(Node oldNode = head;oldNode != null;oldNode = oldNode.next){
            Node newNode = new Node(oldNode.val);
            map.put(oldNode,newNode);
        }
        //3，再次遍历旧链表，建立next和random指向
        for(Node oldNode = head;oldNode != null;oldNode = oldNode.next){
            Node newNode = map.get(oldNode);
            newNode.next = map.get(oldNode.next);
            newNode.random = map.get(oldNode.random);
        }
        //返回新链表的头节点
        return map.get(head);
    }
}
